﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Runtime.CompilerServices;

namespace Alogrithm
{
    public class PriorityQueue
    {
        public int[] GetOrder(int[][] tasks)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            var result = new int[tasks.Length];
            var sortByTimeTasks = new List<Queue>(tasks.Length);
            //WaitList = new List<Queue>(tasks.Length);
            Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
            for (var i = 0; i < tasks.Length; i++)
            {
                sortByTimeTasks.Add(new Queue { Time = tasks[i][0], Process = tasks[i][1], Index = i });
                // SortByTimeIndex(sortByTimeTasks, new Queue { Time = tasks[i][0], Process = tasks[i][1], Index = i });
            }
            //Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
            sortByTimeTasks.Sort();
            Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
            var duration = sortByTimeTasks[0].Time;
            var complete = 0;
            var inTimeTasks = new List<Queue>(tasks.Length);
            //Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
            while (complete < result.Length)
            {
                
                if (sortByTimeTasks.Count > 0)
                {
                    if (inTimeTasks.Count == 0 && duration < sortByTimeTasks[0].Time)
                    {
                        duration = sortByTimeTasks[0].Time;
                    }
                    if (duration >= sortByTimeTasks[0].Time)
                    {
                        inTimeTasks = SortByProcessIndex(inTimeTasks, GetWaitTasks(sortByTimeTasks, duration));
                        //inTimeTasks.AddRange(GetWaitTasks(sortByTimeTasks, duration));
                        //Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
                        //inTimeTasks.Sort(new ProcessComparable());
                        //Console.WriteLine("Stopwatch总共花费{0}ms.", sw.Elapsed.TotalMilliseconds);
                    }
                }
                duration += (duration >= inTimeTasks[0].Time ? 0 : inTimeTasks[0].Time) + inTimeTasks[0].Process;
                //Console.Write("dur:"+duration+",");
                result[complete++] = inTimeTasks[0].Index;
                inTimeTasks.RemoveAt(0);
            }

            return result;
        }
        //private List<Queue> WaitList;

        private List<Queue> SortByProcessIndex(List<Queue> tasks, List<Queue> nTasks)
        {
            var i = 0;
            var j = 0;
            if (nTasks.Count == 1)
            {
                while (tasks[i++].Process > nTasks[0].Process)
                {
                    tasks.Add(tasks[i]);
                }
                return tasks;
            }
            var WaitList = new List<Queue>(tasks.Count + nTasks.Count);
            //WaitList.Clear();
            while (i < tasks.Count && j < nTasks.Count)
            {
                if (tasks[i].Process < nTasks[j].Process)
                {
                    WaitList.Add(tasks[i++]);
                }
                else if (tasks[i].Process == nTasks[j].Process)
                {
                    WaitList.Add(tasks[i].Index < nTasks[j].Index ? tasks[i++] : nTasks[j++]);
                }
                else
                {
                    WaitList.Add(nTasks[j++]);
                }
            }

            while (i < tasks.Count)
            {
                WaitList.Add(tasks[i++]);
            }

            while (j < nTasks.Count)
            {
                WaitList.Add(nTasks[j++]);
            }

            return WaitList;
        }

        private void SortByTimeIndex(List<Queue> tasks, Queue nTask)
        {
            if (tasks.Count == 0)
            {
                tasks.Add(nTask);
                return;
            }

            var i = 0;
            while (i < tasks.Count)
            {
                if (tasks[i].Time >= nTask.Time)
                {
                    tasks.Insert(i, nTask);
                    return;
                }
                i++;
            }

            if (i == tasks.Count)
            {
                tasks.Add(nTask);
            }
        }




        private List<Queue> GetWaitTasks(List<Queue> tasks, int duration)
        {
            var result = new List<Queue>(tasks.Count);
            var i = 0;
            while (i < tasks.Count)

            {
                if (tasks[i].Time <= duration)
                {
                    result.Add(tasks[i]);
                    tasks.RemoveAt(i);
                }
                else
                {
                    break;
                }
            }
            return result.OrderBy(i => i.Process).ThenBy(i => i.Index).ToList();
        }

        public class Queue : IComparable<Queue>
        {
            public int Index { get; set; }
            public int Time { get; set; }
            public int Process { get; set; }

            public int CompareTo(Queue other)
            {
                if (Time > other.Time)
                {
                    return 1;
                }
                if (Time == other.Time)
                {
                    return 0;
                }
                return -1;
            }
        }
        public class ProcessComparable : IComparer<Queue>
        {
            public int Compare(Queue x, Queue y)
            {
                if (x.Process > y.Process)
                {
                    return 1;
                }
                if (x.Process == y.Process)
                {
                    if (x.Index > y.Index)
                    {
                        return 1;
                    }
                    else {
                        return -1;
                    }
              
                }
                return -1;
            }
        }
    }
}